#include "BTreeNode.h"
#include <iostream>

using namespace std;
const int MAXKEYS = 84;			// 84 * 12 = 1008 bytes + 8 for PageId and keyCount so 1016



// Structure of Leaf Node

/*----------------------------------------------------------------------------
Key Count || Next Pointer || Key, RecordId || Key, RecordId || ...      
/*----------------------------------------------------------------------------

/**
 * Class constructor for BTLeafNode, fills buffer with null bytes
 */
BTLeafNode::BTLeafNode()
{
	// zero out the buffer on creating a node
	memset(buffer, '\0', PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	// zero out buffer again if we are going to write to it
	memset(buffer, '\0', PageFile::PAGE_SIZE);
	
	
	return pf.read(pid,buffer);		// reads into the buffer
									// will return 0 if successful
									// will return error code from the read if error
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid,buffer);	// writes from buffer into page file
									// will return 0 if successful
									// will return error code from teh write if error
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	int keyCount;
	
	// We will store the key count in the beginning of the buffer so it's easier to maintain
	memcpy(&keyCount, &buffer, sizeof(int));
	
	return keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */

RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int size = 0;
	char* p = buffer;
	char temp[PageFile::PAGE_SIZE];
	memset(temp, '\0', PageFile::PAGE_SIZE);
	
	// Goes past the key count and next page id pointer in the beginning of buffer
	p += sizeof(int);
	p += sizeof(PageId);
	
	// This gets the size based on the number of entries
	size = getKeyCount() * (sizeof(RecordId) + sizeof(int));
	
	/*
	* Didn't work when debugging
	 
	 while(buffer[size] != '\0')		// to get the size of data in buffer already
	 size++;
	 
	 if((size + sizeof(rid) + sizeof(key)) > PageFile::PAGE_SIZE)	// this means that there is not enough space in the page to add this
	 return -1;		// -1 is error code for not enough room
	 else
	 {
	 int eid;
	 if(locate(key, eid) == -1)		// find where key should be placed, if -1 that means can't be found so place at end
	 {
	 int start = size - sizeof(PageId);		// Since PageId is at the end, have to insert it before the PageId
	 memcpy(temp, (p + start), size - start);		// store values in temp array so can insert new record id and key
	 memcpy((p+start), &rid, sizeof(RecordId));		// store record id
	 memcpy((p+start+sizeof(RecordId)), &key, sizeof(int));	// store key
	 memcpy((p+start+sizeof(RecordId))+sizeof(int), temp, size - start);		// restore data that was moved temporarily to insert new record id and key
	 }
	 else
	 {
	 int start = eid * (sizeof(RecordId) + sizeof(int));
	 memcpy(temp, (p + start), size - start);		// store values in temp array so can insert new record id and key
	 memcpy((p+start), &rid, sizeof(RecordId));		// store record id
	 memcpy((p+start+sizeof(RecordId)), &key, sizeof(int));	// store key
	 memcpy((p+start+sizeof(RecordId))+sizeof(int), temp, size - start);		// restore data that was moved temporarily to insert new record id and key
	 }
	 return 0;
	 }
	 
	 */
	
	if(getKeyCount() >= MAXKEYS)
		return RC_NODE_FULL;
	
	int numEntries = 0;

	int eid;
	if(locate(key, eid) != 0)
	{
		numEntries = getKeyCount();
	}
	else
	{
		numEntries = eid;
	}
		
	int copySize = (sizeof(RecordId) + sizeof(int)) * numEntries;
	
	p += copySize;

		
	// copy into the temp array
	memcpy(temp, p, size - copySize);
	memset(p, '\0', size - copySize);
	
	// copy new entry
	memcpy(p, &key, sizeof(int));
	p += sizeof(int);
	memcpy(p, &rid, sizeof(RecordId));
	
	p += sizeof(RecordId);

	memcpy(p, temp, size - copySize);		// copy back from the temporary array

	
	// set the new key count by increasing the key count by 1
	int curKeyCount = getKeyCount() + 1;
	p = buffer;
	// write the new key count to the buffer
	memcpy(p, &curKeyCount, sizeof(int));
	
	return 0;
}
 
/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	
	int size = 0; 
	char* p = buffer;
	char temp[PageFile::PAGE_SIZE];	
	char* temp1 = temp;
	p += sizeof(int);
	p += sizeof(PageId);
	
	if(sibling.buffer[0] != '\0')
		return -1;			// error since sibling node must start empty
	
	/*
	 * Didn't work
	 *
	while(buffer[size] != '\0')		// to get the size of data in buffer already
		size++;
	
	if((size + sizeof(rid) + sizeof(key)) > PageFile::PAGE_SIZE)	// this means that there is not enough space in the page to add this
	{
		memcpy(temp, buffer, PageFile::PAGE_SIZE);		// copy the buffer to the larger temporary array
		int tempSize = 0;
		char* p1 = temp;
		char temp1[((PageFile::PAGE_SIZE) + sizeof(RecordId) + sizeof(int))];
		while(temp[tempSize] != '\0')		// to get the size of data in buffer already
			tempSize++;
		
		int eid;
		if(locate(key, eid) == -1)		// find where key should be placed, if -1 that means can't be found so place at end
		{
			int start1 = tempSize - sizeof(PageId);		// Since PageId is at the end, have to insert it before the PageId
			memcpy(temp1, (p1 + start1), tempSize - start1);		// store values in temp array so can insert new record id and key
			memcpy((p1+start1), &rid, sizeof(RecordId));		// store record id
			memcpy((p1+start1+sizeof(RecordId)), &key, sizeof(int));	// store key
			memcpy((p1+start1+sizeof(RecordId))+sizeof(int), temp1, tempSize - start1);		// restore data that was moved temporarily to insert new record id and key
		}
		else
		{
			int start1 = eid * (sizeof(RecordId) + sizeof(int));
			memcpy(temp1, (p + start1), tempSize - start1);		// store values in temp array so can insert new record id and key
			memcpy((p1+start1), &rid, sizeof(RecordId));		// store record id
			memcpy((p1+start1+sizeof(RecordId)), &key, sizeof(int));	// store key
			memcpy((p1+start1+sizeof(RecordId))+sizeof(int), temp1, tempSize - start1);		// restore data that was moved temporarily to insert new record id and key
		}
		
		int half = (getKeyCount()+1) / 2;		// This will return the eid of the halfway point
		tempSize += sizeof(rid) + sizeof(key);
		
		int start2;
		start2 = half *  (sizeof(int) + sizeof(RecordId));		// use the index to find starting spot
		memcpy(sibling.buffer, (p1 + start2), tempSize - start2);		// store values in sibling LeafNode
		while(start2 < PageFile::PAGE_SIZE)
		{
			p1[start2] = '\0';			// fill in the part copied in with Null terminated bytes
			start2 ++;
		}
		memcpy(buffer,temp,PageFile::PAGE_SIZE);
		
	}
	else
	{
		insert(key, rid);		// will add key and rid to appropriate spot
		int half = getKeyCount() / 2;		// This will return the eid of the halfway point
		size += sizeof(rid) + sizeof(key);
		
		int start;
		start = half *  (sizeof(int) + sizeof(RecordId));		// use the index to find starting spot
		memcpy(sibling.buffer, (p + start), size - start);		// store values in sibling LeafNode
		while(start < PageFile::PAGE_SIZE)
		{
			p[start] = '\0';			// fill in the part copied in with Null terminated bytes
			start ++;
		}
	}
	*/
	
	size = getKeyCount() * (sizeof(RecordId) + sizeof(int));		// get size of node entries
	int half = getKeyCount() / 2;		// this is the index halfway through
	
	
	// set p to the entry halfway through
	for(int i = 0; i < half; i++)
	{
		p += sizeof(RecordId) + sizeof(int);
	}	
	
	// store the 2nd half of the node so we can insert it into the sibling node

	memcpy(temp1, p, size - ((sizeof(RecordId) + sizeof(int)) * half));
	
	

	// clear old node
	memset(p, '\0', size - ((sizeof(RecordId) + sizeof(int)) * half));
	int newKey = half;		// we now have a new number of keys
	memcpy(buffer, &newKey, sizeof(int));	// so insert the new number of keys into buffer
	

	while(temp1[0] != '\0') 
	{
		int sibkey;
		RecordId r;
		memcpy(&sibkey, temp1, sizeof(int));		// get the sibling key
		
		
		temp1 += sizeof(int);
		memcpy(&r, temp1, sizeof(RecordId));		// get the record
		temp1 += sizeof(RecordId);

		if( sibling.insert(sibkey, r) != 0 )		// insert records into sibling node
			return RC_FILE_WRITE_FAILED;
	}
	
	
	RecordId r;
	if(sibling.readEntry(0, siblingKey, r) != 0)		// read the first entry to get the key of the sibling node
		return RC_FILE_READ_FAILED;
	
	
	if(key < siblingKey) 
	{
		if(insert(key, rid) != 0 )		// if new key that we're trying to insert is less than the sibling key insert it in original node
			return RC_FILE_WRITE_FAILED;
	} 
	else 
	{
		if(sibling.insert(key, rid) != 0 )	// if greater than the sibling key insert it in original node
			return RC_FILE_WRITE_FAILED;
	}
	
	if(sibling.readEntry(0, siblingKey, r) != 0)	// in case the key just entered is the new sibling key
		return RC_FILE_READ_FAILED;
	
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int id = 0;
	int curKey;	
	char* p = buffer;
	
	
	p += sizeof(int);
	p += sizeof(PageId);
	
	while(p[0] != '\0')		// while not at the end of the buffer
	{	
		memcpy(&curKey, p, sizeof(int));		// get new key value
		if(curKey >= searchKey)					// if the new key value is >= to the search key
		{
			eid = id;			// store the current entry number
			return 0;			// return 0
		}
		
		id++;		// increase entry number
		p += sizeof(RecordId) + sizeof(int);	// +8 for record Id
												// +4 for key value
	}
	
	return -1; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	char* p = buffer;
	if(eid < 0)
	{
		return -1;
	}
	int id = 0;
	
	p += sizeof(int);
	p += sizeof(PageId);
	while(p[0] != '\0' && id < eid) 
	{
		p += sizeof(RecordId) + sizeof(int);		// go to next entry
		id++;
	}
	memcpy(&key, p, sizeof(int));
	p += sizeof(int);
	memcpy(&rid, p, sizeof(RecordId));
	
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId nextNode;
	
	char* p = buffer;
	p += sizeof(int);
	
	memcpy(&nextNode, p, sizeof(PageId));		// the next node pointer is after the key count
	
	return nextNode; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	char* p = buffer;
	p += sizeof(int);
	
	memcpy(p, &pid, sizeof(PageId));		// the next node pointer is after hte key count 
	
	return 0; 
}




/**
 * Class constructor for BTNonLeafNode, fills buffer with null bytes
 */
BTNonLeafNode::BTNonLeafNode()
{
	memset(buffer,'\0',PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid,buffer);		// reads into the buffer
									// will return 0 if successful
									// will return error code from the read if error
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid,buffer);	// writes from buffer into page file
									// will return 0 if successful
									// will return error code from teh write if error
}


/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int keyCount;
	
	// We will store the key count in the beginning of the buffer so it's easier to maintain
	memcpy(&keyCount, &buffer, sizeof(int));
	
	return keyCount;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int size = 0;
	int start = 0;
	int curKey;
	char* p = buffer;
	char temp[PageFile::PAGE_SIZE];
	memset(temp, '\0', PageFile::PAGE_SIZE);
	size = getKeyCount() * (sizeof(PageId) + sizeof(int));
	
	if(size < sizeof(int) + sizeof(PageId) + sizeof(int) + sizeof(PageId))
	{
		return -1;			// returns an error if not at least 2 Page Id's and a a key... it should be initialized with root already
	}
	
	else if(size + sizeof(PageId) + sizeof(int) > PageFile::PAGE_SIZE)
	{
		return RC_NODE_FULL;			// returns an error if no space ot insert in NonLeafNode
	}
		
	p += sizeof(int);
	p += sizeof(PageId);
	
	while(p[0] != '\0')	
	{
		memcpy(&curKey,p,sizeof(int));	// This goes past the RecordId, into the key field, and copies the key into the curKey variable
		if(key < curKey)
		{
			memcpy(temp, p, size - start);		// copy the Page id of the PageId before the higher valued key
			memset(p, '\0', size - start);
			memcpy(p, &key, sizeof(int));	// copy key
			p += sizeof(int);
			memcpy(p, &pid, sizeof(PageId));		// copy page id
			p += sizeof(PageId);
			memcpy(p, temp, size - start);	// copy stuff in temp to end of buffer
			
			// set the new key count by increasing the key count by 1
			int curKeyCount = getKeyCount() + 1;
			p = buffer;
			// write the new key count to the buffer
			memcpy(p, &curKeyCount, sizeof(int));
			return 0;
		}
		
		start += sizeof(PageId) + sizeof(int);
		p += start;
	}
		// copies at end since the key is bigger than all the stored keys
	memcpy(p, &key, sizeof(int));				// copy key
	memcpy(p + sizeof(int), &pid, sizeof(PageId));		// copy page id
	
	// set the new key count by increasing the key count by 1
	int curKeyCount = getKeyCount() + 1;
	p = buffer;
	// write the new key count to the buffer
	memcpy(p, &curKeyCount, sizeof(int));
	
	return 0;
	
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int size = 0;
	char* p = buffer;
	char temp[PageFile::PAGE_SIZE];
	memset(temp, '\0', PageFile::PAGE_SIZE);
	char* temp1 = temp;
	int half = getKeyCount() / 2;
	
	p += sizeof(int);		// go past key count
	
	if(sibling.buffer[0] != '\0')
		return -1;			// error since sibling node must start empty
	
	if(size < sizeof(int) + sizeof(PageId) + sizeof(int) + sizeof(PageId))
	{
		return -1;			// returns an error if not at least 2 Page Id's and a a key... it should be initialized with root already
	}
	
	
	memcpy(temp1, p, size - half * (sizeof(PageId) + sizeof(int)));		// copy half of the entries to temp
	memset(p, '\0', size - half * (sizeof(PageId) + sizeof(int)));		// clear end of initial buffer
	
	int newKey = half;		// we now have a new number of keys
	memcpy(buffer, &newKey, sizeof(int));	// so insert the new number of keys into buffer
	
	int curKey;
	PageId pd;
	
	while(temp1[0] != '\0')		
	{
		memcpy(&curKey,temp1,sizeof(int));	
		temp1 += sizeof(int);
		memcpy(&pd, temp, sizeof(PageId));
		temp1 += sizeof(PageId);
	
		if(sibling.insert(curKey,pd) != 0)		// insert entries into sibling
			return RC_FILE_WRITE_FAILED;
	}
	
	
	memcpy(&midKey, sibling.buffer + sizeof(int) + sizeof(PageId), sizeof(int));	// this gets the first key of the sibling
	
	// And now insert the key
	if(key < midKey)		// if less than the middle key, insert into original node
	{
		if( insert(key, pd) != 0 )
			return RC_FILE_WRITE_FAILED;
	} 
	else					// if greater than or equal to the middle key, insert it into the sibling node
	{
		if( sibling.insert(key, pd) != 0 )
			return RC_FILE_WRITE_FAILED;
	}
	
	
	return 0; 	
}
		

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int curKey;
	char* p = buffer;

	p += sizeof(int);
	p += sizeof(PageId);
	
	while(p[0] != '\0')
	{
		memcpy(&curKey, p, sizeof(int));
		
		if(searchKey < curKey)
		{
			memcpy(&pid, p - sizeof(PageId), sizeof(PageId));
			return 0;
		}
		p += sizeof(PageId) + sizeof(int);
	}
	
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{

	char* p = buffer;
	p += sizeof(int);
	int one = 1;
	
	memcpy(p, &pid1, sizeof(PageId));
	p += sizeof(PageId);
	memcpy(p, &key, sizeof(int));
	p += sizeof(int);
	memcpy(p, &pid2, sizeof(PageId));
	memcpy(buffer, &one, sizeof(int));		// set the root key count to be 1
	return 0;
}
